/*
 * 栈的链式存储
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


/* type */
struct Student {
    int id;
    char name[100];
    int age;
    char sex;
};
typedef struct Student ElemType;
//typedef int ElemType;


struct node {
    ElemType data;
    struct node *next;
};

struct link_stack {
    struct node *top;
    int count;
};

typedef struct link_stack link_stack_t;


/*
 * 初始化栈
 */
void
init_stack(link_stack_t *stack)
{
    stack->top = NULL;
    stack->count = 0;
}

int
get_stack_length(link_stack_t *stack)
{
    return stack->count;
}

int
is_stack_empty(link_stack_t *stack)
{
    return stack->count == 0;
}

int
get_stack_top_item(link_stack_t *stack, ElemType *item)
{
    if (stack->count == 0)
        return -1;

    *item = stack->top->data;

    return 0;
}


/*
 * 入栈：不需要头结点
 */
int
push(link_stack_t *stack, ElemType *item)
{
    struct node *ptr;
    ptr = (struct node *) malloc(sizeof(struct node));

    ptr->next = stack->top;
    ptr->data = *item;
    stack->top = ptr;
    ++stack->count;

    return 0;
}

/*
 * 出栈：不需要头结点
 */
int
pop(link_stack_t *stack, ElemType *item)
{
    /* if empty */
    if (stack->count == 0)
        return -1;

    struct node *ptr;
    ptr = stack->top;

    *item = ptr->data;
    stack->top = ptr->next;
    free(ptr);
    --stack->count;

    return 0;
}


int
clear_stack(link_stack_t *stack)
{
    ElemType item;

    while (stack->count != 0)
        pop(stack, &item);
}




/******************************************************************************/


int
main(void)
{
    link_stack_t stack;
    int i, ret;
    ElemType item;

    init_stack(&stack);

    printf("After init, length = %d\n", get_stack_length(&stack));
    printf("After init, is_stack_empty = %d\n", is_stack_empty(&stack));

    /* 插入10个节点 */
    for (i = 0; i < 10; ++i) {
        memset(&item, 0, sizeof(item));
        item.id = i+1;
        snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
        printf("push() item[%d] ret[%d]\n", i, push(&stack, &item));
    }
    printf("\n");
    printf("After push, length = %d\n", get_stack_length(&stack));
    printf("After push, is_stack_empty = %d\n", is_stack_empty(&stack));


    printf("\n");
    memset(&item, 0, sizeof(item));
    get_stack_top_item(&stack, &item);
    printf("After push, top item: Stu_id[%d], Stu_Name[%s]\n", item.id, item.name);



    printf("\n");
    /* 弹出15个节点 */
    for (i = 0; i < 15; ++i) {
        memset(&item, 0, sizeof(item));
        ret = pop(&stack, &item);
        printf("pop() item[%d] ret[%d]\n", i, ret);
        if (ret == 0)
            printf("-- Stu_id[%d], Stu_Name[%s]\n", item.id, item.name);
    }
    printf("After pop, length = %d\n", get_stack_length(&stack));
    printf("After pop, is_stack_empty = %d\n", is_stack_empty(&stack));


    clear_stack(&stack);
    clear_stack(&stack);

    printf("\n");
    printf("After clear, length = %d\n", get_stack_length(&stack));
    printf("After clear, is_stack_empty = %d\n", is_stack_empty(&stack));


    /* 插入5个节点 */
    for (i = 0; i < 5; ++i) {
        memset(&item, 0, sizeof(item));
        item.id = i+1;
        snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
        printf("push() item[%d] ret[%d]\n", i, push(&stack, &item));
    }
    printf("\n");
    printf("After push, length = %d\n", get_stack_length(&stack));
    printf("After push, is_stack_empty = %d\n", is_stack_empty(&stack));

    memset(&item, 0, sizeof(item));
    get_stack_top_item(&stack, &item);
    printf("After push, top item: Stu_id[%d], Stu_Name[%s]\n", item.id, item.name);


    while ((pop(&stack, &item)) != -1)
        printf("pop(): Stu_id[%d], Stu_Name[%s]\n", item.id, item.name);
    printf("After pop, length = %d\n", get_stack_length(&stack));
    printf("After pop, is_stack_empty = %d\n", is_stack_empty(&stack));


    return 0;
}



